package com.clps.algorithm.chapter14.字符串交织;

public class isInterleave_01 {

    public static void main(String[] args) {

    }


    public  boolean isInterLeave(String s1,String s2,String s3){
        if(s1.length() + s2.length()!=s3.length()){
            return  false;
        }


        if(s1.length() < s2.length()){
            return  isInterLeave(s2,s1,s3);
        }


        boolean[] dp = new boolean[s2.length() + 1];
        dp[0] = true;

        for (int j = 0; j < s2.length(); j++) {
            dp[j+1] = s2.charAt(j) == s3.charAt(j) && dp[j];
        }


        for (int i = 0; i <s1.length() ; i++) {
            dp[0] = dp[0] && s1.charAt(i) == s3.charAt(i);

            for (int j = 0; j < s2.length(); j++) {
                char ch1 = s1.charAt(i);
                char ch2 = s2.charAt(j);
                char ch3 = s3.charAt(i+j+1);
                dp[j+1] = (ch1 == ch3 && dp[j + 1])
                    || ( ch2 == ch3 && dp[j]);
            }
        }

        return  dp[s2.length()];
    }
}
